#include<iostream>
#include<cmath>
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<vector>
#include<set>
#include <unordered_map>
using namespace std;
template <class k>
class bsnode
{
public:
    k _val;
    bsnode* left;
    bsnode* right;
    bsnode(k val):
        _val(val),
        left(nullptr),
        right(nullptr)
    {} 
};
template <class k>
class bstree
{
    typedef bsnode<k> node;
private:
    node* _root = nullptr;
    void inorder(node* cur)//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
    {

        if (cur == nullptr) return;
        inorder(cur->left);             // 先递归遍历左子树
        cout << cur->_val << ' ';       // 再输出当前节点值
        inorder(cur->right);            // 最后递归遍历右子树
    }
public:
    void inorder()//这是外层
    {
        inorder(_root);
    }
    node* find(const k& key)
    {
        node* pcur = _root;
        if (pcur == nullptr) {
            return nullptr;
        }
        while(pcur)
        {
            if (key < pcur->_val)
            {
                pcur = pcur->left;
            }
            else if (key > pcur->_val)
            {
                pcur = pcur->right;
            }
            else return pcur;
        }
        return nullptr;
    }
    bool insert(const k& key)
    {
        node* newnode=new node(key);
        node* pcur = _root;
        if (pcur == nullptr) {
            _root = newnode;
            return true;
        }
        while(pcur)
        {
            if (key < pcur->_val)
            {
                if (pcur->left == nullptr) { pcur->left = newnode; return true; }
                else pcur = pcur->left;
            }
            else if (key > pcur->_val)
            {
                if (pcur->right == nullptr) { pcur->right = newnode; return true; }
                else pcur = pcur->right;
            }
            else return false;
        }
        return false;
    }
    bool erase(const k& key)
    {
        node* pcur = _root;
        node* father = _root;
        if (father == nullptr) {
            return false;
        }
        while (pcur)
        {
            if (key < pcur->_val)
            {
                father = pcur;
                pcur = pcur->left;
            }
            else if (key > pcur->_val)
            {
                father = pcur;
                pcur = pcur->right;
            }
            else
            {
                if (pcur == _root)
                {
                    node* tmp = _root;
                    if (pcur->left == nullptr)
                    {
                        _root = _root->right;
                        delete(tmp);
                        return true;
                    }
                    else if (pcur->right == nullptr)
                    {
                        _root = _root->left;
                        delete(tmp);
                        return true;
                    }
                    else
                    {
                        node* fcur = pcur->right;
                        node* cur = pcur->right;
                        while (cur->left) {
                            fcur = cur;
                            cur = cur->left;
                        }
                        pcur->_val = cur->_val;
                        if (fcur == cur) pcur->right = cur->right;
                        else fcur->left = cur->right;
                        delete(cur);
                        return true;
                    }
                }
                else
                {
                    if (pcur->left == nullptr)
                    {
                        if (key < father->_val)
                            father->left = pcur->right;
                        else father->right = pcur->right;
                        delete(pcur);
                        return true;
                    }
                    else if (pcur->right == nullptr)
                    {
                        if (key < father->_val)
                            father->left = pcur->left;
                        else father->right = pcur->left;
                        delete(pcur);
                        return true;
                    }
                    else
                    {
                        node* fcur = pcur->right;
                        node* cur = pcur->right;
                        while (cur->left) {
                            fcur = cur; 
                            cur = cur->left;
                        }
                        pcur->_val = cur->_val;
                        if (fcur == cur) pcur->right = cur->right;
                        else fcur->left = cur->right;
                        delete(cur);
                        return true;
                    }
                }
            }
        }
        return false;
    }
};
int main()
{
    int ch[5] = { 13,4,1,2,5 };
    bstree<int> bst;
    for (int i = 0; i < 5; i++)
        bst.insert(ch[i]);
    bst.erase(13);
    bst.inorder();
    return 0;
}